

#include <iostream>
using namespace std;

class Solution
{
public:
    bool validPalindrome1(string s)
    {
        int n = s.size();
        if (1 == n)
            return true;

        int flag = 1;
        for (int i = 0, j = n - 1; i < j; ++i, --j)
        {
            if (s[i] != s[j])
            {
                flag = 0;
                break;
            }
        }
        if (flag)
            return true;

        
        for (int i = 0; i < n; ++i)
        {
            flag = 1;
            for (int beg = 0, end = n - 1; beg < end; ++beg, --end)
            {
                if (beg == i)
                    ++beg;
                if (end == i)
                    --end;
                if (s[beg] != s[end])
                {
                    flag = 0;
                    break;
                }
            }
            if (flag)
                return true;
        }

        return false;
    }

    bool validPalindrome2(string s)
    {
        int n = s.size();
        if (1 == n)
            return true;

        for (int beg = 0, end = n - 1; beg < end; ++beg, --end)
        {
            if (s[beg] != s[end])
            {
                return _validPalindrome2(s, beg + 1, end) || _validPalindrome2(s, beg, end - 1);
            }
        }

        return true;
    }

    int mySqrt1(int x)
    {
        int res = 0;

        for (int lf = 0, rg = x, mid = 0; lf <= rg;)
        {
            mid = lf + ((rg - lf) >> 1);
            if (mid * mid > x)
                rg = mid - 1;
            else if (mid * mid < x)
                lf = mid + 1;
            else
            {
                res = mid;
                break;
            }
        }

        return res;
    }

    int mySqrt2(int x)
    {
        if (!x || 1 == x)
            return x;

        int lf = 0, rg = x;

        for (int mid = 0; lf <= rg;)
        {
            mid = lf + ((rg - lf) >> 1);

            if ((long long)mid * mid > x)
                rg = mid - 1;
            else if ((long long)mid * mid < x)
                lf = mid + 1;
            else
                return mid;
        }

        return rg;
    }

private:
    bool _validPalindrome2(const string& s, int beg, int end)
    {
        for (; beg < end; ++beg, --end)
        {
            if (s[beg] != s[end])
                return false;
        }

        return true;
    }
};

void Test1()
{
    Solution().validPalindrome2("abca");
    Solution().mySqrt(8);
}

int main()
{
    Test1();

	return 0;
}